package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-12 18:41
 **/
public class LeetCode1020 {

    int m;
    int n;
    boolean[][] visited;
    static final int[][] DIRS = new int[][]{{0,1},{0,-1},{-1,0},{1,0}};

    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        //从所有和网格边界相邻的陆地格出发,最后遍历所有陆地格,如果未被访问过,则说明其是飞地
        for (int i = 0; i < m; ++i) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }

        for (int i = 1; i < n - 1; ++i) {
            dfs(grid, 0, i);
            dfs(grid, m - 1, i);
        }

        int res = 0;
        //记录飞地数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    ++res;
                }
            }
        }
        return res;
    }

    void dfs(int[][] grid, int i, int j) {
        if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1 && !visited[i][j]) {
            visited[i][j] = true;
            for (int[] dir : DIRS) {
                int x = i + dir[0];
                int y = j + dir[1];
                dfs(grid, x, y);
            }
        }
    }

}
